﻿// 122. 糖果传递.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>

using namespace std;
/*

https://www.acwing.com/problem/content/124/

有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为 1。

求使所有人获得均等糖果的最小代价。

输入格式
第一行输入一个正整数 n，表示小朋友的个数。

接下来 n 行，每行一个整数 a[i]，表示第 i 个小朋友初始得到的糖果的颗数。

输出格式
输出一个整数，表示最小代价。

数据范围
1≤n≤1000000,
0≤a[i]≤2×109,
数据保证一定有解。

输入样例：
4
1
2
5
4
输出样例：
4
*/

const int N = 1000010;
long long arr[N]; long long  s[N]; long long c[N];
int n;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) { cin >> arr[i]; }
	for (int i = 1; i <= n; i++) { s[i] = s[i - 1] + arr[i]; }
	long long avg = s[n] / n;
	c[1] = 0;
	for (int i = 2; i <= n; i++) { c[i] = s[i - 1] - (i - 1) * avg; }
	long long  res = 0;
	sort(c+1,c+1+n);
	for (int i = 1; i <= n; i++) res += abs(c[i] - c[(n + 1) / 2]);

	cout << res << endl;
	return 0;
}

 